/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
// recursive
// 1. while left and right tree are all balanced;
// 2. |h(root.Left) - h(root.Right)| <= 1;
func isBalanced(root *TreeNode) bool {
	// quit cond
	if root == nil {
		return true
	}

	if !isBalanced(root.Left) || !isBalanced(root.Right) {
		return false
	}

	// how to get height of root.Left and root.Right
	if intAbs(maxDepth(root.Left), maxDepth(root.Right)) <= 1 {
		return true
	}

	return false
}

func intAbs(a, b int) int {
	if a < b {
		return b - a
	}
	return a - b
}

func maxDepth(root *TreeNode) int {
	// quit cond
	if root == nil {
		return 0
	}

	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}